package _02_linked_list.exerc.merge;

import _02_linked_list.exerc.ListNode;
import _02_linked_list.exerc.ListNodeBuilder;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/3 - 16:43
 * 合并多个有序的链表
 * <p>
 *          [1,2] [1,3]  = [1,1,1,2,3]
 *          []      []   = []
 *          []      [1]  = [1]
 */
public class MyTest2 {

    @Test
    public void test() {
        ListNode list1 = ListNodeBuilder.of(new int[]{1, 1, 2});
        ListNode list2 = ListNodeBuilder.of(new int[]{1, 3, 12});
        ListNode list3 = ListNodeBuilder.of(new int[]{1, 3, 12});
        ListNode[] arr = {list1, list2, list3};
//        System.out.println(mergeMulti(arr));
        System.out.println(mergeMulti2(arr));

    }

    @Test
    public void testMulti() {
        int len = 20;
        ListNode[] arr = new ListNode[len];
        for (int i = 0; i < len; i++) {
            arr[i] = ListNodeBuilder.of(new int[]{i});
        }
        System.out.println(mergeMulti(arr));
    }

    /**
     * 合并多个有序链表
     *
     * @param arr
     * @return
     */
    ListNode mergeMulti(ListNode... arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }

        //  0  1  2
        // [] [] []
        ListNode t = arr[0];
        for (int i = 1; i < arr.length; i++) {
            t = merge(t, arr[i]);
        }
        return t;

//        int i = 0;
//        for (; i < arr.length - 1; i++) {
//            arr[i + 1] = foo1(arr[i], arr[i + 1]);
//        }
//        return arr[i]; // arr[0];

//        int index = 0;
//        for (int i = index; i < arr.length - 1; i++) {
//            arr[index + 1] = foo2(arr[index], arr[index + 1]);
//            index = i + 1;
//        }
//        return arr[index];
    }

    /**
     * 递归合并（分治）
     *
     * @param arr
     * @return
     */
    ListNode mergeMulti2(ListNode... arr) {
        if (arr.length == 0) {
            return null;
        }
        return split(arr, 0, arr.length - 1);
    }

    ListNode split(ListNode[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        int m = (i + j) >>> 1;
        ListNode left = split(arr, i, m);
        ListNode right = split(arr, m + 1, j);
        return merge(left, right);
    }

    ListNode merge(ListNode list1, ListNode list2) {
        ListNode s = new ListNode();
        /*
            s 表示创建的新链表，存储 list1 + list2 合并的数据
            p 表示 s 中最后一个非空元素下标，下次插入直接指定 p.next
         */
        ListNode p = s;
        ListNode p1 = list1;
        ListNode p2 = list2;

        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return s.next;
    }
}
